package backtracking;

import java.util.Scanner;

/**
 * 
 * @author victor
 * 
 */
public class PermutacionesBacktracking {

	/**
	 * 
	 * @param args
	 */
	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		
		try {
			int numero = Integer.parseInt( sc.nextLine() );
			
			permutaciones( numero );
			
		} catch(Exception e){
			;
		}
	}
	
	/**
	 * 
	 * @param n
	 */
	private static void permutaciones(int n) {
		int[] perm = new int[n];
		boolean[] libres = new boolean[n];
		for (int i = 0; i < n; i++)
			libres[i] = true;
		perms(n, 0, perm, libres);
	}

	/**
	 * 
	 * @param v
	 */
	private static void imprimir(int[] v) {
		for (int i = 0; i < v.length; i++)
			System.out.print(v[i] + " ");
		System.out.println();
	}

	/**
	 * 
	 * @param n
	 * @param i
	 * @param solucion
	 * @param xs
	 */
	private static void perms(int n, int i, int[] solucion, boolean[] xs) {
		for (int k = 0; k < n; k++)
			if (xs[k]) {
				solucion[i] = k;
				xs[k] = false;

				if (i == n - 1)
					imprimir(solucion);
				else
					perms(n, i + 1, solucion, xs);

				xs[k] = true;
			}
	}

}
